package com.gitee.feizns.dynamic.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 树操作工具类
 * @author feizns
 * @since 2025/1/2
 */
public class Trees {

    /**
     * 构建树
     * @param nodes 节点
     * @return {@link List}<{@link T}>
     */
    public static <ID, T extends Node<T, ID>> List<T> build(List<T> nodes) {
        return new Builder<>(nodes).build(Node::getId, Node::getParentId, Node::getChildren);
    }

    /**
     * 构建树
     * @param nodes 节点
     * @param idFunc 编号函数
     * @param parentIdFunc 父编号函数
     * @param childrenFunc 子节点函数
     * @return {@link List}<{@link T}>
     */
    public static <T> List<T> build(List<T> nodes, Function<T, ?> idFunc, Function<T, ?> parentIdFunc, Function<T, List<T>> childrenFunc) {
        return new Builder<>(nodes).build(idFunc, parentIdFunc, childrenFunc);
    }

    /**
     * 遍历映射
     * @param node 节点
     * @param childrenFunc 子节点列表映射
     * @param mappingFunc 映射函数
     * @return {@link List}<{@link U}>
     */
    public static <T, U> List<U> map(T node, Function<T, List<T>> childrenFunc, Function<T, U> mappingFunc) {
        List<U> result = new ArrayList<>();
        result.add(mappingFunc.apply(node));
        List<T> children = childrenFunc.apply(node);
        for (T child : children)
            result.addAll(map(child, childrenFunc, mappingFunc));
        return result;
    }

    /**
     * 遍历
     * @param node 节点
     * @param childrenFunc 子节点列表
     * @param consumer 消费者
     */
    public static <T> void each(T node, Function<T, List<T>> childrenFunc, Consumer<T> consumer) {
        consumer.accept(node);
        List<T> children = childrenFunc.apply(node);
        for (T child : children)
            each(child, childrenFunc, consumer);
    }

    /**
     * 打平树形
     * @param node 节点
     * @param childrenFunc 子节点列表
     * @return {@link List}<{@link T}>
     */
    public static <T> List<T> flat(T node, Function<T, List<T>> childrenFunc) {
        return map(node, childrenFunc, Function.identity());
    }

    /**
     * 建筑构建者
     * @author feizns
     * @since 2025/01/02
     */
    private static class Builder<T> {

        /**
         * 值
         */
        private final List<T> values;

        /**
         * 父编号映射
         */
        private Map<Object, List<T>> parentIdMap;

        /**
         * 构建者
         * @param values 值
         */
        public Builder(List<T> values) {
            this.values = values;
        }

        /**
         * 建
         * @param idFunc 编号函数
         * @param parentIdFunc 父编号函数
         * @param childrenFunc 子节点列表函数
         * @return {@link List}<{@link T}>
         */
        public List<T> build(Function<T, ?> idFunc, Function<T, ?> parentIdFunc, Function<T, List<T>> childrenFunc) {
            //编号映射表
            Map<Object, T> idMap = values.stream().collect(Collectors.toMap(idFunc, Function.identity(), (o, n) -> n));
            this.parentIdMap = values.stream().collect(Collectors.groupingBy(parentIdFunc));
            List<T> roots = new ArrayList<>();
            //查找所有的根节点
            for (Map.Entry<Object, List<T>> entry : this.parentIdMap.entrySet()) {
                if ( !idMap.containsKey(entry.getKey()) )
                    roots.addAll(entry.getValue());
            }
            return build(roots, idFunc, childrenFunc);
        }

        /**
         * 建
         * @param roots 根
         */
        private List<T> build(List<T> roots, Function<T, ?> idFunc, Function<T, List<T>> childrenFunc) {
            for (T root : roots) {
                Object id = idFunc.apply(root);
                List<T> children = childrenFunc.apply(root);
                children.addAll(parentIdMap.getOrDefault(id, Collections.emptyList()));
                //对子节点进行构建
                build(children, idFunc, childrenFunc);
            }
            return roots;
        }

    }

}
